# 第4节关键道路-图的割边
# 和第三节不同在于
# 1low[i] >= num[cur] 改成low[i] > num[cur]
# 2输出部分line36
n = 6
m = 7
e = [[0 for i in range(0, 10)] for i in range(0, 10)]
num = [0 for i in range(0, 10)]
low = [0 for i in range(0, 10)]
flag = [0 for i in range(0, 10)]
index = 0  # 用来进行时间数的递增
root = 1


# 求两个数比较小一个数的函数
# python 已经支持
# 算法核心
def dfs(cur, father):
    # child用来记录在生成树中当前顶点cur的儿子个数
    child, i, j = 0, 0, 0
    global index
    index += 1  # 时间戳自增
    num[cur] = index  # 当前顶点cur的时间戳
    low[cur] = index  # 当前项点cur能够访问到最早顶点的时间默，刚开始当然是自己啦
    # 枚举与当前项点cur有边相连的项点i
    for i in range(1, n + 1):
        if e[cur][i] == 1:
            if num[i] == 0:  # 如果顶点i的时问戳不为0。说明顶点i还没有被访问过
                child += 1
                dfs(i, cur)  # 继续往下深度优先遍历
                # 更新当前顶点cur能否访问到最早顶点的时间戳
                low[cur] = min(low[cur], low[i])
                # 如果当前顶点不是根结点并且满足1ow[i】 >= num[cur]，则当前顶点为割点
                if cur != root and low[i] > num[cur]:
                    flag[cur] = 1
                    print('%d - %d' % (cur, i))
                # 如果当前顶点是根结点。在生成树中根结点必须要有两个儿子，那么这个根结点才是割点
                if cur == root and child == 2:
                    flag[cur] = 1

            elif i != father:
                # 否则如果顶点i曾经被访问过，井且这个顶点不是当前顶点cur的父亲，则需要更新当前结点cur能否访问到最早顶点的时间戳
                low[cur] = min(low[cur], num[i])


if __name__ == '__main__':
    print('start')
    a = [[1, 4], [1, 3], [4, 2], [3, 2], [2, 5], [5, 6]]
    for i, v in enumerate(a):
        # print(v)
        e[v[0]][v[1]] = 1
        e[v[1]][v[0]] = 1
    # 深度优先
    # 从1号顶点开始进行深度优光遍历
    dfs(1, root)
    # 打印结果
    # for i, v in enumerate(flag):
    #     if v == 1:
    #         print(i)
